#include <bits/stdc++.h>
using namespace std;
class Solution
{
  int lcp(string &s, string &t)
  {
    int n = min(s.size(), t.size());
    for (int i = 0; i < n; i++)
    {
      if (s[i] != t[i])
        return i;
    }
    return n;
  }

public:
  vector<int> longestCommonPrefix(vector<string> &words)
  {
    int n = words.size();
    vector<int> ans(n);
    if (n == 1)
      return ans;

    // 求后缀
    vector<int> back_max(n);
    // 尾巴单元素无 即0 不用进入循环
    // 表示下标i后的元素组的最大lcp
    for (int i = n - 2; i > 0; i -= 1)
      back_max[i] = max(back_max[i + 1], lcp(words[i], words[i + 1]));
    int pre_max = 0;
    // 左端点无左侧 值为后缀最大lcp值
    ans[0] = back_max[1];
    for (int i = 1; i < n - 1; i++)
    {
      ans[i] = max(
          {pre_max, lcp(words[i - 1], words[i + 1]), back_max[i + 1]});
      pre_max = max(pre_max, lcp(words[i], words[i - 1]));
    }
    ans[n - 1] = pre_max;
    return ans;
  }
};
int main()
{
  Solution s;

  return 0;
}
